package _17_剑指Offer;

public class _13_剑指Offer机器人的运动范围 {

    public static void main(String[] args) {

        _13_剑指Offer机器人的运动范围 v = new _13_剑指Offer机器人的运动范围();

        System.out.println(v.movingCount(3, 1, 0));

    }

    private int[][] vertex = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1},
    };

    private int rows;

    private int cols;

    private int target;

    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        this.rows = m;
        this.cols = n;
        this.target = k;
        return dfs(visited, 0, 0);
    }

    public int dfs(boolean[][] visited, int row, int col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col] || row / 10 + row % 10 + col / 10 + col % 10 > target) return 0;
        // 在下面都是合法内容
        int count = 1;
        visited[row][col] = true;
        for (int[] ints : vertex) {
            count += dfs(visited, row + ints[0], col + ints[1]);
        }
        return count;
    }

}
